A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Computer networks may have parallel data paths. For example, a network may have a number of interconnected intermediate devices that provide connectivity from an inbound edge router to an outbound edge router. Similarly, a communication device within a computer network may have multiple internal data paths. For example, two network routers may be connected by multiple Ethernet links. Similarly, multiple physical interconnects may couple other devices, e.g., two switches, a switch and a server, two routers, a switch and an end user station, and the like. As a result, some of the packets traveling between two network devices may make use of one path, while other packets traveling between the same two network devices may make use of one or more alternate paths.
The sequence in which a device receives the packets may be important. For instance, a device may need to receive the packets in the sequence the source device sent the packets. Example applications that require in-sequence delivery include support of the Asynchronous Transfer Mode (ATM) over router networks, link emulation using the Internet Protocol (IP) or the Multiprotocol Label Switching (MPLS) protocol, and High-Level Data Link Control (HDLC) over IP or MPLS. Traffic may arrive out of order if packets belonging to the same packet flow are communicated using alternate paths. Further, the traffic may not be distributed evenly among the paths, which may result in congestion on one data path and unused bandwidth on another. This may decrease the efficiency of the network and increase packet latency.
Conventional techniques for load balancing across parallel data paths can generally be classified in one of two categories: per-packet load balancing and per-packet flow load balancing. In the first category, the methods load balance individual packets, i.e., send packets of the same flow over different links to balance the bandwidth consumed from the different physical links. These methods run a risk of delivering packets of a packet flow out of order. For example, one per-packet distribution method includes deterministically rotating among the parallel data paths when transmitting packets, e.g., sending packets along different ones of the parallel data paths in a round-robin fashion. Although this method balances loads across the data paths, packets are highly likely to arrive out of order, causing this receiving device to re-order the packets. As a result, the receiving device must buffer the packets to place them in order before transmitting the packets. All of these conditions require extra hardware and/or software in the network devices implementing these methods
In the second category, per-packet flow distribution methods aim to solve the noted problems of per-packet distribution by sending packets of a common packet flow across the same one of the parallel data paths. In general, these distribution methods apply a hash function to the packets to select one of the parallel data paths for a new packet flow. This can prevent packet reordering within a flow, but can lead to inefficient usage of links as flows can be assigned to a heavily loaded link even though other links are not used. Further, per-packet flow methods require tracking a vast array of characteristics of packet flows through the network in an attempt to ensure packets of the same flow traverse the same links while still allowing load balancing across multiple links. This requires maintenance of a massive data structure, such as a flow-to-link map table, to track the individual packet flows in real time. These methods require a large diversion of processing power and memory for maintaining the data structure. These methods also tend to result in inefficient bandwidth allocation among the links, and may result in a congested link receiving new packet flows although other links remain unused at the time of the new packet flow.